#include "Graph.h"

Graph::Graph(int MaxCities_)
{
	_numberCities = 0;
	_maxCities = MaxCities_;
	_city = new City[MaxCities_];
	_routes = new int*[MaxCities_];
	for(int i = 0; i < MaxCities_; i++)
		_routes[i] = new int[MaxCities_];

	for (int i = 0; i < _maxCities; i++)
		for (int j = 0; j < _maxCities; j++)
			_routes[i][j] = 0;
}
														
void Graph::makeEmpty()
{
	/*
	for(int i=0; i < _maxCities; i++)
		_city[i].index = 0;
	*/
	for(int i = 0; i < _maxCities; i++)
	{
		for(int j = 0; j < _maxCities; j++)
			_routes[i][j] = 0;
	}
	_numberCities = 0;
}

bool Graph::isEmpty() const
{
	return (_numberCities == 0);
}

bool Graph::isFull() const
{
	return (_numberCities == _maxCities);
}
										/*         A Problem !! Check   "<="     */
void Graph::addCity(string cityName)
{
	assert(_numberCities <= _maxCities);

	_city[_numberCities]._name = cityName;

	_city[_numberCities]._index = _numberCities;

	_numberCities++;
}

void Graph::addRoute(City firstCity_, City secondCity_, int weight_)
{
	int row;
	int column;
	row = firstCity_._index;
	column = secondCity_._index;
	_routes[row][column] = weight_;
	_routes[column][row] = weight_;
}

void Graph::removeRoutes()
{
	for (int i = 0; i < _maxCities; i++)
	{
		for (int j = i + 1; j < _maxCities; j++)
		{
			_routes[i][j] = 0;
			_routes[j][i] = 0;
		}
	}
}

int Graph::weight_Is(City firstCity_, City secondCity_)
{
	int row;
	int column;
	row = firstCity_._index;
	column = secondCity_._index;
	return _routes[row][column];
}

void Graph::getNeighboursCities(City city_, Queue& cities_)
{
	int fromIndex;
	int toIndex;

	fromIndex = city_._index;

	for(toIndex = 0; toIndex < _numberCities; toIndex++)
	{
		if(_routes[fromIndex][toIndex] != 0)
			cities_.Enqueue(_city[toIndex]);
	}
}

void Graph::clearMarks()
{
	for(int i=0; i < _maxCities; i++)
		_city[i]._marked = false;
}

void Graph::markCity(City city_)
{
	city_._marked = true;
}

bool Graph::isMarked(City city_) const
{
	return ( city_._marked == true );
}

Graph* Graph::getMST(City city_)
{
	Graph *mst;
	int  x, y;
	int min = numeric_limits<int>::max();
	//bool *selected;

	mst = new Graph(_numberCities);
	
	//initialize mst by vertices
	for (int i = 0; i < _numberCities; i++)
		mst->addCity(_city[i]._name);

	//enable it to check it's edges
	_city[city_._index]._marked = true;

	//selected = new bool[_numberCities];
	//for (int i = 0; i < _numberCities; i++)
	//	selected[i] = false;


	for (int k = 0; k < _numberCities; k++)
	{
		for (int i = 0; i < _numberCities; i++)
		{
			if(_city[i]._marked == true)
			{
				//detect minimum adjacent edge form index city
				for (int j = 0; j < _numberCities; j++)
				{
					if(_city[j]._marked == false && _routes[j][i] > 0 && _routes[j][i] < min)
					{
						min = _routes[j][i];
						x = i;
						y = j;
					}
				}
			}
		}

		if (_city[y]._marked == false)
		{
			_city[y]._marked = true;
	
			//add min edge to mst
			mst->_routes[y][x] = min;
			mst->_routes[x][y] = min;
		}

		min = numeric_limits<int>::max();
	}

	clearMarks();

	return mst;
}

City* Graph::getNearestCity(City city_)
{
	int index = city_._index;
	int minIndex = -1;
	int minValue = numeric_limits<int>::max();
	
	for (int i = 0; i < _numberCities; i++)
	{
		if( _routes[index][i] < minValue && _routes[index][i] != 0 )
		{
			minValue = _routes[index][i];
			minIndex = i;
		}
	}

	if( minIndex >= 0 )
		return &_city[minIndex];

	return nullptr;
}

int Graph::getShortestPath(City cityFrom_, City cityTo_, Queue& cities_)
{
	int index = cityFrom_._index;
	int *dist, *edgeFrom;
	int sum;
	int min = 0;

	dist = new int[_numberCities];
	edgeFrom = new int[_numberCities];

	for (int i = 0; i < _numberCities; i++)
		dist[i] = numeric_limits<int>::max();

	//distance from source to source equal zero
	dist[index] = 0;

	//detect shorts distances -dist[]- of adjacent cities from my location (source) -city-
	for (int i = _numberCities; i > 0; i--)
	{
		//detect shorts distances -dist[]- of adjacent cities from current index -city-
		for (int j = 0; j < _numberCities; j++)
		{
			if (_routes[j][index] > 0 && !_city[j]._marked)
			{
				sum = dist[index] + _routes[j][index];
				
				//check if number in dist is bigger than sum to replace it by a new value of a new path -route-
				if (sum < dist[j])
				{
					dist[j] = sum;
					edgeFrom[j] = index;	//detect vertex -city- it come from
				}
			}


		}

		_city[index]._marked = true;
		
		min = 0;

		//detect index of minimum egde -route- to be my next start if i don't reach to distenation yet
		if (_city[index]._index != cityTo_._index)
		{
			for (int j = 0; j < _numberCities; j++)
			{
				if (!_city[j]._marked && dist[j] != numeric_limits<int>::max())
				{
					if (min == 0)	//this check is valid only at the first
					{
						min = dist[j];
						index = j;
					}
					else if (min > dist[j])
					{
						index = j;
						min = dist[j];
					}
				}
			}
		}
		else
			break;
	}

	//sigma weight of the shortest path
	sum = dist[index];

	//detect shortest path
	while (true)
	{
		cities_.Enqueue(_city[index]);

		if (index == cityFrom_._index)
			break;

		index = edgeFrom[index];
	}

	delete [] dist;
	delete [] edgeFrom;

	clearMarks();

	return sum;

		//for (int j = index; j < _numberCities; j)
		//{
		//int i = 0;
		//for (; i < _numberCities; i++)
		//{
		//	if (index == cityFrom_._index)
		//	{
		//		cities_.Enqueue(_city[index]);
		//		break;
		//	}
		//	else if (_routes[j][index] > 0 && _city[j]._marked)
		//	{
		//		if (dist[index] - _routes[j][index] == dist[j])
		//		{
		//			number = dist[index] - _routes[j][index];
		//			cities_.Enqueue(_city[j]);
		//		}
		//	}
		//}
		//if (index == cityFrom_._index)
		//	break;
	//}
}

City* Graph::getCity(string name_)
{
	for(int i = 0 ; i < _numberCities; i++)
	{
		if(_city[i]._name == name_)
			return &_city[i];
	}

	return nullptr;
}

void Graph::showCities()
{
	for(int i = 0; i < _numberCities; i++)
		cout << _city[i]._name << endl;
	cout << endl;
}

void Graph::showGraph()
{
	for(int i = 0; i < _numberCities; i++)
		for (int j = i + 1; j < _numberCities; j++)
			if (_routes[i][j] > 0)
				cout << _city[i]._name << " --(" << weight_Is(_city[i], _city[j]) << ")-- "<< _city[j]._name << endl;
	cout << endl;
}

void Graph::showNeighbours( City city_)
{
	Queue cities_;
	getNeighboursCities(city_, cities_);
	
	cout << "Neighbours : " << endl;
	while ( ! cities_.isEmpty() )
	{
		cout << city_._name << " --(" << weight_Is( city_, cities_.peekHead() ) << ")-- "<< cities_.peekHead()._name << endl;
		cities_.Dequeue();
		//cout << cities_.peekHead()._name << " : " << weight_Is( city_, cities_.Dequeue() ) <<endl;
	}
	cout << endl;
}

Graph::~Graph()
{
	delete [] _city;
	for(int i = 0; i < _maxCities; i++)
		delete [] _routes[i];
	delete [] _routes;
}